#ifndef _UTIL_RED_BLACK_TREE_
#define _UTIL_RED_BLACK_TREE_

#ifdef __cplusplus
extern "C" {
#endif

#include "utilc_def.h"
#include "utilc_string.h"
#include <stdint.h>

typedef enum e_util_rb_tree_color {
    UTIL_RB_TREE_COLOR_RED, UTIL_RB_TREE_COLOR_BLACK
}util_rb_tree_color_t;

typedef struct s_util_rb_tree_node {
    struct s_util_rb_tree_node* _pt_parent;
    struct s_util_rb_tree_node* _pt_left;
    struct s_util_rb_tree_node* _pt_right;
    util_rb_tree_color_t        _t_color;
    void*                       value;
}util_rb_tree_node_t;

typedef struct s_util_rb_tree {
    util_rb_tree_node_t    _t_rbroot;
    size_t                 _t_nodecount;

    COMPAIR_FUN            _t_compare;
    DESTORY_FUN            fun_destory;
}util_rb_tree_t;


typedef struct s_util_rb_tree_iter {
    util_rb_tree_t      *tree;
    util_rb_tree_node_t *node;
} util_rb_tree_iter_t;

util_rb_tree_t* util_rb_tree_create(COMPAIR_FUN fun_compare);

void util_rb_tree_destory(util_rb_tree_t *tree);

uint32_t util_rb_tree_size(const util_rb_tree_t *tree);

void util_rb_tree_clear(util_rb_tree_t* tree);

bool util_rb_tree_empty(const util_rb_tree_t *tree);

uint32_t util_rb_tree_count(const util_rb_tree_t* tree, const void* value);

uint32_t util_rb_tree_remove(util_rb_tree_t* tree, const void* value);

util_rb_tree_iter_t* util_rb_tree_begin();
util_rb_tree_iter_t* util_rb_tree_next(util_rb_tree_iter_t *iter);
util_rb_tree_iter_t* util_rb_tree_erase(util_rb_tree_iter_t *iter);

#ifdef __cplusplus
}
#endif
#endif